/*
 * Copyright (c) 2011 Robert Kirchgessner <rkirchge@gmail.com>
 *                    Carlo Pascoe <carlo.pascoe@gmail.com>
 * 
 * Permission is hereby granted, free of charge, to any person obtaining a copy
 * of this software and associated documentation files (the "Software"), to deal
 * in the Software without restriction, including without limitation the rights
 * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
 * copies of the Software, and to permit persons to whom the Software is
 * furnished to do so, subject to the following conditions:
 * 
 * The above copyright notice and this permission notice shall be included in
 * all copies or substantial portions of the Software.
 * 
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
 * THE SOFTWARE.
 */

#include <stdint.h>
#include <sys/queue.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
#include <stdio.h>

#include "debug.h"
#include "subgraphoverlay.h"
#include "graph.h"

void
overlay_init(struct overlaygraph *og)
{
  og->size = 0;
  LIST_INIT(&og->subgraphs);
}

void
overlay_cleanup(struct overlaygraph *og)
{
  struct subgraph *sg, *sg_next;
  struct overlay_vertice *ov, *ov_next;
  struct overlay_edge *e, *e_next;

  sg = LIST_FIRST(&og->subgraphs);
  while(sg) {
    sg_next = LIST_NEXT(sg, next);

    ov = LIST_FIRST(&sg->vertices);
    while(ov) {
      ov_next = LIST_NEXT(ov, next);
      free(ov);
      ov = ov_next;
    }
    
    e = LIST_FIRST(&sg->edges);
    while(e) {
      e_next = LIST_NEXT(e, next);
      free(e);
      e = e_next;
    }
    free(sg);
    sg = sg_next;
  }

}

struct subgraph *
overlay_insert_subgraph(struct overlaygraph *og)
{
  struct subgraph *sg;
  sg = (struct subgraph *)malloc(sizeof(struct subgraph));
  assert(sg != NULL);
  og->size++;
  LIST_INSERT_HEAD(&og->subgraphs, sg, next);
  LIST_INIT(&sg->edges);
  LIST_INIT(&sg->vertices);
  return sg;
}

void overlay_subgraph_add_vertice(struct subgraph *sg, struct vertice *v)
{
  struct overlay_vertice *ov;
  ov = (struct overlay_vertice *)malloc(sizeof(struct overlay_vertice));
  ov->v = v;
  LIST_INSERT_HEAD(&sg->vertices, ov, next); 
}

void 
overlay_subgraph_edge(struct subgraph *sg0, struct subgraph *sg1)
{
  struct overlay_edge *oe;
  uint32_t flux = 0;

  struct overlay_vertice *v0, *v1;
  struct edge *edge;

  //OMG Loops -- but we need to see what vertices have common edges
  //in the actual graph. As long as the number of actual edges and
  //subgraph size is small, this O(V1*E1*V2) process should be fast
  LIST_FOREACH(v0, &sg0->vertices, next) {
    LIST_FOREACH(edge, &v0->v->edges, next) {
      LIST_FOREACH(v1, &sg1->vertices, next) {
        if(edge->v == v1->v) {
	  flux++;
	}
      }
    }
  }

  //Cannot be an edge if they have no graph edge in common...
  if(flux == 0) {
    return;
  }

  oe = (struct overlay_edge *)malloc(sizeof(struct overlay_edge));
  oe->flux = flux;
  oe->sg = sg1;
  LIST_INSERT_HEAD(&sg0->edges, oe, next);

  oe = (struct overlay_edge *)malloc(sizeof(struct overlay_edge));
  oe->flux = flux;
  oe->sg = sg0;
  LIST_INSERT_HEAD(&sg1->edges, oe, next);
}

struct overlay_edge * 
overlay_get_edge(struct subgraph *sg0, struct subgraph *sg1)
{
  struct overlay_edge *oe;
  //OMG Loops -- but we need to see what vertices have common edges
  //in the actual graph
  LIST_FOREACH(oe, &sg0->edges, next) {
    if(oe->sg == sg1) {
      return oe;
    }
  }
  return NULL;
}

LIST_HEAD(candidate_list, overlay_vertice);

/**
 * @brief Generate a list of vertices sorted by degree
 */
static uint32_t 
_generate_degree_list(struct graph *g, struct candidate_list *candidate_vertices)
{
  struct overlay_vertice *ov, *v_curr;
  struct vertice *v;
  uint32_t count = 0;

  LIST_FOREACH(v, &g->vertices, next) {
    v_curr = LIST_FIRST(candidate_vertices); 
    ov = (struct overlay_vertice *)malloc(sizeof(struct overlay_vertice));
    ov->v = v;

    if(v_curr == NULL || v->degree > v_curr->v->degree) {
      LIST_INSERT_HEAD(candidate_vertices, ov, next);
      count ++;
    }
    else {
      while(v_curr) {
        if(LIST_NEXT(v_curr, next) == NULL || v->degree >= LIST_NEXT(v_curr, next)->v->degree) {
	  LIST_INSERT_AFTER(v_curr, ov, next);
	  count++;
	  break;
	}
	v_curr = LIST_NEXT(v_curr, next);
      }
    }
  }
  return count;
}

static struct overlay_vertice * 
_find_vertex(struct candidate_list *candidate_vertices, struct vertice *v)
{
  struct overlay_vertice *ov;

  LIST_FOREACH(ov, candidate_vertices, next) {
    if(ov->v == v) {
      return ov;
    }
  }
  return NULL;
}

static struct overlay_vertice *
_get_random_vertice_old(struct subgraph *sg, struct candidate_list *candidate_vertices, uint32_t candidates, uint32_t size)
{
  struct overlay_vertice *ov, **ov_list, *ov_candidate, *ov_tmp;
  struct edge *e;
  struct vertice  *v;
  uint32_t candidate_count, degree, selected, found;
  struct overlay_vertice *ret;

  //If the subgraph list is empty, we select the first candidate (highest degree)
  if(LIST_FIRST(&sg->vertices) == NULL) {
    return LIST_FIRST(candidate_vertices);
  }

  //Iterate over all vertices currently in the subgraph
  LIST_FOREACH(ov, &sg->vertices, next) {
    candidate_count = 0;
    v = ov->v;

    degree = graph_get_degree(v);
    if(degree > 0) {
      ov_list = (struct overlay_vertice **)malloc(sizeof(struct overlay_vertice *) * degree);
    }

    assert(ov_list != NULL);

    //Iterate over all edges of the selected vertice to select next candidate
    LIST_FOREACH(e, &v->edges, next) {

      //Check if the vertex is the candidate_vertices list
      if((ov_candidate = _find_vertex(candidate_vertices, e->v)) != NULL) {
        //Iterate over all vertices in the subgraph to make sure the current node is not in the subgraph
	found = 0;
        LIST_FOREACH(ov_tmp, &sg->vertices, next) {
	  if(ov_tmp->v == ov_candidate->v) {
	    found = 1;
	  }
	}

	//Make sure the vertice is not already in the subgraph
	if(!found) {
          ov_list[candidate_count++] = ov_candidate; 
        }
      }
    }

    //Number of candidates found
    if(candidate_count > 0) {
      selected = rand() % candidate_count;
      ret = ov_list[selected];
      free(ov_list);
      return ret;
    }
    if(ov_list) {
      free(ov_list);
    } 
  }
  return NULL;
}

static struct overlay_vertice *
_get_random_vertice_priority(struct subgraph *sg, struct candidate_list *candidate_vertices, uint32_t candidates, uint32_t size)
{
  struct overlay_vertice *ov, *ret, **ov_list;
  struct edge *e;
  uint32_t candidate_count, selected;

  //If the subgraph list is empty, we select the first candidate (highest degree)
  if(LIST_FIRST(&sg->vertices) == NULL) {
    return LIST_FIRST(candidate_vertices);
  }

  uint32_t allocated = 10 + size/3;
  ov_list = (struct overlay_vertice **)malloc(allocated * sizeof(struct overlay_vertice *));
  assert(ov_list != NULL);

  candidate_count = 0;
  //Iterate over all vertices currently in the subgraph
  LIST_FOREACH(ov, &sg->vertices, next) {
    //Iterate over the edges of all vertices in the subgraph
    LIST_FOREACH(e, &ov->v->edges, next) {
      //Check if the vertice is a candidate
      if((ret =_find_vertex(candidate_vertices, e->v)) != NULL) {
        ov_list[candidate_count++] = ret;
	if(candidate_count == allocated) {
	  allocated = 2 * allocated;
	  ov_list = realloc(ov_list, allocated * sizeof(struct overlay_vertice *));
	  assert(ov_list != NULL);
	}
      }
    }
  }

  if(candidate_count == 0) {
    free(ov_list);
    return NULL;
  }

  //Select a candidate node
  selected = rand() % candidate_count;
  ret = ov_list[selected];
  free(ov_list);

  return ret;
}


static struct overlay_vertice *
_get_vertice_priority(struct subgraph *sg, struct candidate_list *candidate_vertices, uint32_t candidates, uint32_t size)
{
  struct overlay_vertice *ov, *ret, **ov_list;
  struct edge *e;
  uint32_t candidate_count;

  //If the subgraph list is empty, we select the first candidate (highest degree)
  if(LIST_FIRST(&sg->vertices) == NULL) {
    return LIST_FIRST(candidate_vertices);
  }

  uint32_t allocated = 10 + size/3;
  ov_list = (struct overlay_vertice **)malloc(allocated * sizeof(struct overlay_vertice *));
  assert(ov_list != NULL);

  candidate_count = 0;
  //Iterate over all vertices currently in the subgraph
  LIST_FOREACH(ov, &sg->vertices, next) {
    //Iterate over the edges of all vertices in the subgraph
    LIST_FOREACH(e, &ov->v->edges, next) {
      //Check if the vertice is a candidate
      if((ret =_find_vertex(candidate_vertices, e->v)) != NULL) {
        ov_list[candidate_count++] = ret;
	if(candidate_count == allocated) {
	  allocated = 2 * allocated;
	  ov_list = realloc(ov_list, allocated * sizeof(struct overlay_vertice *));
	  assert(ov_list != NULL);
	}
      }
    }
  }

  if(candidate_count == 0) {
    free(ov_list);
    return NULL;
  }

  //Select candidate node, greedy style
  int i, max, degree, tie_counter;
  for(i=0, max=-1; i<candidate_count; i++) {
    if((degree = graph_get_degree(ov_list[i]->v)) > max) {
      tie_counter = 0;
      ov_list[0] = ov_list[i];
      max = degree;
    }
    else if(degree == max) {
      ov_list[tie_counter++] = ov_list[i];
    }
  }

  ret = ((tie_counter>0)?(ov_list[rand() % (tie_counter+1)]):ov_list[0]);
  free(ov_list);
  return ret;
}

static struct overlay_vertice *
_get_random_vertice(struct subgraph *sg, struct candidate_list *candidate_vertices, uint32_t candidates, uint32_t size)
{
  struct overlay_vertice *ov, *ret, **ov_list;
  struct edge *e;
  uint32_t candidate_count, selected;

  if(LIST_FIRST(&sg->vertices) == NULL) {
    selected = rand() % candidates;
    //Iterate over the candidate list and return the selected
    //vertice
    LIST_FOREACH(ov, candidate_vertices, next) {
      if(selected == 0) {
        return ov;
      }
      selected--;
    }
    assert(0);
  }

  uint32_t allocated = 10 + size/3;
  ov_list = (struct overlay_vertice **)malloc(allocated * sizeof(struct overlay_vertice *));
  assert(ov_list != NULL);
 
  candidate_count = 0;
  //Iterate over all vertices currently in the subgraph
  LIST_FOREACH(ov, &sg->vertices, next) {
    //Iterate over the edges of all vertices in the subgraph
    LIST_FOREACH(e, &ov->v->edges, next) {
      //Check if the vertice is a candidate
      if((ret =_find_vertex(candidate_vertices, e->v)) != NULL) {
        ov_list[candidate_count++] = ret;
	if(candidate_count == allocated) {
	  allocated = 2 * allocated;
	  ov_list = realloc(ov_list, allocated * sizeof(struct overlay_vertice *));
	  assert(ov_list != NULL);
	}
      }
    }
  }

  if(candidate_count == 0) {
    free(ov_list);
    return NULL;
  }

  //Select a candidate node
  selected = rand() % candidate_count;
  ret = ov_list[selected];
  free(ov_list);

  return ret;
}

void
generate_subgraph_overlay(struct graph *g, struct overlaygraph *og, uint32_t method, uint32_t k)
{
  struct subgraph *sg, *sg_next;
  struct candidate_list candidate_vertices;
  LIST_INIT(&candidate_vertices);

  struct overlay_vertice *ov, *ov_selected;
  struct vertice *v;
  uint32_t i;

  struct overlay_vertice * (*overlay_select)(struct subgraph *sg, struct candidate_list *candidate_vertices, uint32_t candidates, uint32_t size);

  //Set the method for selecting vertices
  switch(method) {
    case METHOD_RANDOM_PRIORITY:
      overlay_select = _get_random_vertice_priority;
      break;
    case METHOD_DEGREE_PRIORITY:
      overlay_select = _get_vertice_priority;
      break;
    case METHOD_RANDOM:
      overlay_select = _get_random_vertice;
      break;
    case METHOD_OLD:
      overlay_select = _get_random_vertice_old;
      break;
  };
  
  uint32_t candidates;
  candidates = _generate_degree_list(g, &candidate_vertices);
  debug("Generated degree list\n", NULL);

  //Remove the first candidate vertice
  ov = LIST_FIRST(&candidate_vertices);
  while(ov) {
    sg = overlay_insert_subgraph(og);

    //Select k-1 other vertices from the candidate list which 
    //form a connected subgraph
    for(i=0; i<k; i++) {
      debug("Selecting random vertice...\n", NULL);
      ov_selected = overlay_select(sg, &candidate_vertices, candidates, g->size);
      debug("Random vertice selected!\n", NULL);

      //If we return NULL, then no vertice could be selected
      if(ov_selected == NULL) {
        break;
      }

      //Remove the selected vertice from the candidate list
      LIST_REMOVE(ov_selected, next);
      candidates--;
      v = ov_selected->v;
      free(ov_selected);

      //Add newly selected vertice
      overlay_subgraph_add_vertice(sg, v);
    }

    debug("found subgraph size: %d\n", i); 
    ov = LIST_FIRST(&candidate_vertices);
  }

#ifdef _ENABLE_DEBUG_
  uint32_t counter = 0;
  LIST_FOREACH(sg, &og->subgraphs, next) {
    counter++;
  }
  debug("Found %d subgraphs\n", counter);
#endif

  //Build subgraph connections
  LIST_FOREACH(sg, &og->subgraphs, next) {
    sg_next = LIST_NEXT(sg, next);
    //Iterate over every subsequent subgraph and try
    //to add any edges
    while(sg_next) {
      overlay_subgraph_edge(sg, sg_next); 
      sg_next = LIST_NEXT(sg_next, next);
    }
  }

}

void
overlay_print(struct overlaygraph *og)
{
  struct subgraph *sg;
  struct overlay_vertice *ov;
  uint32_t count = 0;

  LIST_FOREACH(sg, &og->subgraphs, next) {
    count ++;
    printf("s%d : ", count);
    LIST_FOREACH(ov, &sg->vertices, next) {
      printf("%d", ov->v->id);
      if(LIST_NEXT(ov,next) != NULL) {
        printf(","); 
      }
    }
    printf("\n");
  }
}

void
_write_subgraph_dotty(FILE *fp, struct subgraph *sg, uint32_t id)
{
  struct overlay_vertice *ov, *ov_next;
  struct edge *e;

  fprintf(fp, "subgraph cluster_s%d {\n", id);
  fprintf(fp, "label = \"subgraph %d\"\n", id);

  //For each vertice in the subgraph
  LIST_FOREACH(ov, &sg->vertices, next) {
   fprintf(fp,"%d\n", ov->v->id);
   LIST_FOREACH(e, &ov->v->edges, next) {
     
     //Check all vertices from v+1 to N
     ov_next = LIST_NEXT(ov, next);
     while(ov_next) {
       if(e->v->id == ov_next->v->id) {
         fprintf(fp, "%d -- %d\n", ov->v->id, ov_next->v->id);
       }
       ov_next = LIST_NEXT(ov_next, next);
     }
   }
 }
 fprintf(fp, "}\n\n");
}

void
_write_subgraph_edges_dotty(FILE *fp, struct subgraph *sg0, struct subgraph *sg1)
{
  struct overlay_vertice *ov0, *ov1;
  struct edge *e;

  LIST_FOREACH(ov0, &sg0->vertices, next) {
    LIST_FOREACH(e, &ov0->v->edges, next) {
      LIST_FOREACH(ov1, &sg1->vertices, next) {
        if(e->v->id == ov1->v->id) {
	  fprintf(fp, "%d -- %d\n", ov0->v->id, ov1->v->id);
	}
      }
    }
  }

}

void
overlay_write_dotty(const char *fname, struct overlaygraph *og)
{
  struct subgraph *sg, *sg_next;
  FILE *fp;
  uint32_t count = 0;

  fp = fopen(fname, "w");
  assert(fp != NULL);

  fprintf(fp, "graph overlay_graph {\n");

  //Draw subgraph clusters
  LIST_FOREACH(sg, &og->subgraphs, next) {
    _write_subgraph_dotty(fp, sg, count++);
  }

  LIST_FOREACH(sg, &og->subgraphs, next) {
    sg_next = LIST_NEXT(sg, next);
    while(sg_next) {
       _write_subgraph_edges_dotty(fp, sg, sg_next);
      sg_next = LIST_NEXT(sg_next, next);
    }
  }

  fprintf(fp, "}\n\n");

  fclose(fp);
}

void
overlay_subgraph_adj(struct subgraph *sg, uint32_t *adj, uint32_t k)
{
  struct overlay_vertice *ov, *ov_next;
  uint32_t x, y;

  memset(adj, 0, k*k*sizeof(uint32_t));
  x=0;
  LIST_FOREACH(ov, &sg->vertices, next) {
    ov_next = ov;
    y=x;
    while(ov_next) {
      if(graph_is_adjacent(ov->v, ov_next->v)) {
        adj[COORD(x,y,k)] = 1;
	adj[COORD(y,x,k)] = 1;
      }
      y++;
      ov_next = LIST_NEXT(ov_next, next);
    }
    x++;
  }
}

